package net.tp.struct.tree;

import net.tp.util.Wrappers;
import java.util.*;

/**
 *
 * @author Trung Phan
 *
 */
public abstract class AbstractBinNode<N extends AbstractBinNode<N>> {

    /**
     * Parent node. Null if this node is root.
     */
    public N parent;

    /**
     * Left child node.
     */
    public N left;

    /**
     * Right child node.
     */
    public N right;

    /**
     * Size of the tree from this node. This is not necessary for most algorithms.
     * Size is used in randomized binary search tree to calculate probability.
     * Size is also used to calculate dynamic order statistics: rank or ith item.
     */
    public int size = 1;

    /**
     * Make the node as the left child of this node. Set its parent to this node.
     *
     * @param child external node
     * @return child node
     */
    @SuppressWarnings("unchecked")
    public N bindLeft(N child) {
        this.left = child;
        if (child != null) child.parent = (N)this;
        return child;
    }

    /**
     * Make the node as the right child of this node. Set its parent to this node.
     *
     * @param child external node
     * @return child node
     */
    @SuppressWarnings("unchecked")
    public N bindRight(N child) {
        this.right = child;
        if (child != null) child.parent = (N)this;
        return child;
    }

    
    /**
     * Make these nodes the children of this node. Set their parent to this node.
     *
     * @param children children nodes (left and right nodes)
     *
     */
    public void bindChildren(Iterable<N> children) {
        int i = 0;
        for (N child : children) {
            if (i == 0) bindLeft(child);
            else if (i == 1) bindRight(child);
            else break;
            i++;
        }
    }

    /**
     * Get the root of this tree.
     * @return tree root
     */
    @SuppressWarnings("unchecked")
    public N getRoot() {
        for (AbstractBinNode<N> root = this;; root = root.parent) {
            if (root.parent == null) return (N)root;
        }
    }

    /**
     * Update the size of this node based on the size of its children.
     * @time $O(1)$
     */
    public void updateSize() {
        this.size = 1 + (this.left != null ? this.left.size : 0) + (this.right != null ? this.right.size : 0);
    }

    /**
     * Update the size of this node and all of its ancestor nodes.
     * @time $O(\node \depth)$
     */
    public void updateSizeCascade() {
        for (AbstractBinNode<N> n = this; n != null; n = n.parent) {
            n.updateSize();
        }
    }

    /**
     * Recalculate size of all the nodes in the tree rooted at this node.
     *
     * @time $O(n)$
     * @return size of this node
     */
    public int recalcSize() {
        int leftSize = left == null ? 0 : left.recalcSize();
        int rightSize = right == null ? 0 : right.recalcSize();
        this.size = leftSize + 1 + rightSize;
        return size;
    }

    /**
     * Rotate right.
     *
     * Rotate this node with its left child, moving its left child up.
     *
     * @return the node that is moved up
     *
     */
    @SuppressWarnings("unchecked")
    public N rotateRight() {
        if (left == null) throw new IllegalStateException("Cannot rotate right if left child is null");
        N grandparent = parent;
        N target = left;

        if (grandparent != null) {
            if (grandparent.left == this) grandparent.bindLeft(target);
            else if (grandparent.right == this) grandparent.bindRight(target);
        }
        else {
            target.parent = null;
        }

        this.bindLeft(target.right);
        target.bindRight((N)this);

        this.updateSize();
        target.updateSize();

        return target;
    }

    /**
     * Rotate left.
     *
     * Rotate this node with its right child, moving its right child up.
     *
     * @return the node that is moved up
     */
    @SuppressWarnings("unchecked")
    public N rotateLeft() {
        if (right == null) throw new IllegalStateException("Cannot rotate left if right child is null");
        N grandparent = parent;
        N target = right;

        if (grandparent != null) {
            if (grandparent.left == this) grandparent.bindLeft(target);
            else if (grandparent.right == this) grandparent.bindRight(target);
        }
        else {
            target.parent = null;
        }

        this.bindRight(target.left);
        target.bindLeft((N)this);

        this.updateSize();
        target.updateSize();

        return target;
    }

    /**
     * Rotate.
     *
     * Rotate this node with its parent node. If this node is the left child of its parent, then
     * this is equivalent to rotating the parent node right. If this node is the right child of
     * its parent, then this is equivalent to rotating the parent node left.
     */
    public void rotate() {
        if (parent == null) throw new IllegalStateException("Cannot rotate if parent is null");

        if (parent.left == this) {
            parent.rotateRight();
        }
        else if (parent.right == this) {
            parent.rotateLeft();
        }
        else {
            throw new IllegalStateException("Invalid parent node.");
        }
    }

    /**
     * The iterable of left and right children. If this is leaf, then return the empty iterable, else return the iterable of both left and right children (one of which can be null).
     * @return iterable of left and right children
     */
    public Iterable<N> getChildren() {
        if (isLeaf()) return Collections.emptyList();
        else return Wrappers.makeIterable(left, right);
    }

    /**
     * Determine if this node is a leaf.
     * @return true if this node is a leaf
     */
    public boolean isLeaf() {
        return left == null && right == null;
    }

}
